#pragma once
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<list>
#include<limits>
#include<stack>
#include<set>
#include<queue>
#include<vector>
#include<deque>
#include<unordered_map>
#include <functional>
#include<cstring>

class FastRW {
public:
	int fastReadI() {
		int ans = 0;
		bool flag = 0;
		char c;
		while ((c = getchar()) < '0' || c > '9') {
			flag |= c == '-';
		}
		do {
			ans = (ans << 1) + (ans << 3) + (c ^ 48);
		} while ((c = getchar()) >= '0' && c <= '9');
		if (flag)ans = -ans;
		return ans;
	}

	long long fastReadL() {
		long long ans = 0;
		bool flag = 0;
		char c;
		while ((c = getchar()) < '0' || c > '9') {
			flag |= c == '-';
		}
		do {
			ans = (ans << 1) + (ans << 3) + (c ^ 48);
		} while ((c = getchar()) >= '0' && c <= '9');
		if (flag)ans = -ans;
		return ans;
	}

	char fastReadC() {
		char ans;
		while ((ans = getchar()) <= 32);
		return ans;
	}

	void fastWriteI(int nums) {
		if (nums < 0)putchar('-'), nums = -nums;
		char len = 0;
		do {
			OUTPUT[++len] = nums % 10 | 48;
			nums /= 10;
		} while (nums);
		while (len)putchar(OUTPUT[len--]);
	}

	void fastWriteL(long long nums) {
		if (nums < 0)putchar('-'), nums = -nums;
		char len = 0;
		do {
			OUTPUT[++len] = nums % 10 | 48;
			nums /= 10;
		} while (nums);
		while (len)putchar(OUTPUT[len--]);
	}

	void fastWriteC(char nums) {
		putchar(nums);
	}

private:
	char OUTPUT[40];
};

std::vector<int> _getNext(std::string& pattern) {
	int n = pattern.size();
	std::vector<int> next(n, 0);
	int j = 0;
	for (int i = 1; i < n; i++) {
		while (j > 0 && pattern[i] != pattern[j]) {
			j = next[j - 1];
		}
		if (pattern[i] == pattern[j]) {
			j++;
		}
		next[i] = j;
	}
	return next;
}

std::vector<int> KMP(std::string& text, std::string& pattern) {
	std::vector<int> next = _getNext(pattern);
	std::vector<int> res;
	int m = text.size();
	int n = pattern.size();
	int j = 0;
	for (int i = 0; i < m; i++) {
		while (j > 0 && text[i] != pattern[j]) {
			j = next[j - 1];
		}
		if (text[i] == pattern[j]) {
			j++;
		}
		if (j == n) {
			res.push_back(i - n + 1);
			j = next[j - 1];
		}
	}
	return res;
}

long long fastPower(long long base, long long power, long long mod = 1e9 + 7) {
	long long res = 1 % mod;
	base = base % mod;
	while (power > 0) {
		if (power % 2 == 1) {
			res = (res * base) % mod;
		}
		base = (base * base) % mod;
		power = power / 2;
	}
	return res;
}

std::vector<int> getPrimeList(int left, int right) {
	std::vector<bool> used(right + 1, 1);
	std::vector<int> ans;
	if (right >= 2 && left <= 2)ans.push_back(2);
	for (int i = 3; i <= right; ++i) {
		if (i % 2 == 0)continue;
		if (used[i] == 0)continue;
		for (int j = 2; j * i <= right; ++j) {
			used[j * i] = 0;
		}
		if (i >= left && i <= right)ans.push_back(i);
	}
	return ans;
}

std::vector<bool> getPrime(int upper) {
	std::vector<bool> used(upper + 1, 1);
	used[0] = used[1] = 0;
	for (int i = 3; i <= upper; ++i) {
		if (i % 2 == 0)continue;
		if (used[i] == 0)continue;
		for (int j = 2; j * i <= upper; ++j) {
			used[j * i] = 0;
		}
	}
	return used;
}

class dsu {
private:
	std::vector<int> fa;
	int setCnt = 0;
public:
	dsu(int n) {
		fa.clear();
		fa.resize(n + 1);
		for (int i = 0; i <= n; ++i) {
			fa[i] = i;
		}
		setCnt = n;
	}

	bool isUnited(int x, int y) {
		return find(x) == find(y);
	}

	bool unite(int x, int y) {
		if (isUnited(x, y)) return false;
		setCnt--;
		fa[find(x)] = find(y);
		return true;
	}

	int setCount() {
		return setCnt;
	}

	int find(int x) {
		return fa[x] == x ? x : fa[x] = find(fa[x]);
	}

};